package object;

public class MyBinarySearchTree {
    static class Node {
        public int key;
        public Node left = null;
        public Node right = null;

        public Node(int key) {
            this.key = key;
            this.left = null;
            this.right = null;
        }

        @Override
        public String toString() {
            return "Node{" +
                    "key=" + key +
                    ", left=" + left +
                    ", right=" + right +
                    '}';
        }
    }
    private Node root = null;

    //插入元素
    public void insert(int key) {
        Node newNode = new Node(key);
        if (root == null) {
            root = newNode;
            return;
        }
        Node cur = root;
        Node parent = null;
        while (cur != null) {
           if (key < root.key) {
               parent = cur;
               cur = cur.left;
           } else if (key > root.key) {
               parent = cur;
               cur = cur.right;
           } else {
               return;
           }

        }
        //此时parent就是叶子结点，也就是要插入节的点
        if (key > parent.key) {
            parent.right = newNode;
        } else {
            parent.left = newNode;
        }

    }
    public static void preOrder(Node root) {
        if (root == null) {
            return;
        }
        System.out.print(root.key + " ");
        preOrder(root.left);
        preOrder(root.right);

    }
    public static void inOrder(Node root) {
        if (root == null) {
            return;
        }
        inOrder(root.left);
        System.out.print(root.key + " ");
        inOrder(root.right);
    }
    //根据先序遍历和中序遍历手动还原二叉树
    public void print() {
        preOrder(root);
        System.out.println();
        inOrder(root);
    }
    //查找元素,找到返回其节点,没有,返回null
    public Node find(int key) {
        if (root == null) {
            return null;
        }
        if (key == root.key) {
            return root;
        }
        Node cur = root;
        while (cur != null) {
            if (key < cur.key) {
                cur = cur.left;
            } else if (key > cur.key) {
                cur = cur.right;
            } else {
                return cur;
            }
        }
        return null;
    }
    //删除元素,没找到无事发生
    public void remove(int key) {
        if (root == null) {
            return;
        }
        Node cur = root;
        Node parent = null;
        while (cur != null) {
            if (key < cur.key) {
                parent = cur;
                cur = cur.left;
            } else if (key > cur.key) {
                parent = cur;
                cur = cur.right;
            } else {
                //下面这个用来执行删除元素
                removeNode(parent,cur);
                return;
            }
        }
    }

    private void removeNode(Node parent, Node cur) {
        if (cur.left == null && cur.right == null) {
            if (cur == root) {
                root = null;
                return;
            }
            if (parent.left == cur) {
                parent.left = null;
                return;
            }
            if (parent.right == cur) {
                parent.right = null;
                return;
            }
        }
        if (cur.left != null && cur.right == null) {
            if (cur == root) {
                 root = cur.left;
                 return;
            }
            if (parent.left == cur) {
                parent.left = cur.left;
                return;
            }
            if (parent.right == cur) {
                parent.right = cur.left;
                return;
            }
        }
        if (cur.left == null && cur.right != null) {
            if (cur == root) {
                root = cur.right;
                return;
            }
            if (parent.left == cur) {
                parent.left = cur.right;
                return;
            }
            if (parent.right == cur) {
                parent.right = cur.right;
                return;
            }
        }
        if (cur.left != null && cur.right != null) {
            //此时我们不需要考虑cur == root的情况,因为cur左右子树均存在,此时就不是删除而是修改了
            Node goat = cur.right;
            Node goatParent = cur;
            while (goat.left != null) {
                goatParent = goat;
                goat = goat.left;
            }
            cur.key = goat.key;
            //这里不能直接 goatParent.left = goat.right;
            //要考虑上面循环进不去的情况
            if (goatParent.left == goat) {
                goatParent.left = goat.right;
            } else {
                goatParent.right = goat.right;
            }
        }


    }


    public static void main(String[] args) {
        int[] arr = {1,6,3,5,9,10};
        MyBinarySearchTree myBinarySearchTree = new MyBinarySearchTree();
        for (int i : arr) {
            myBinarySearchTree.insert(i);
        }
        myBinarySearchTree.print();
        System.out.println();
        System.out.println(myBinarySearchTree.find(9));
        System.out.println(myBinarySearchTree.find(0));
        System.out.println();
        myBinarySearchTree.remove(6);
        myBinarySearchTree.print();
    }
}
